# -*- coding: utf-8 -*-
# 堆排序

def heap_sort(array):
    n = len(array)
    last = int(n / 2 - 1)  # 最后一个非叶子节点
    for start in range(last, -1, -1):
        max_heapify(array, start, n - 1)
    for end in range(n - 1, 0, -1):
        array[end], array[0] = array[0], array[end]
        max_heapify(array, 0, end - 1)
    return array


def max_heapify(array, start, end):
    root = start
    while True:
        child = root * 2 + 1  # 调整节点的子节点
        if child > end:
            break
        if child + 1 <= end and array[child] < array[child + 1]:
            child += 1  # 取较大的子节点
        if array[root] < array[child]:  # 较大的子节点成为父节点
            array[root], array[child] = array[child], array[root]  # 交换
            root = child
        else:
            break
